//
//  ProblemOffer55-2.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 55 - II. 平衡二叉树
 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

 示例 1:
 给定二叉树 [3,9,20,null,null,15,7]
     3
    / \
   9  20
     /  \
    15   7
 返回 true 。

 示例 2:
 给定二叉树 [1,2,2,3,3,null,null,4,4]
        1
       / \
      2   2
     / \
    3   3
   / \
  4   4
 返回 false 。

 限制：0 <= 树的结点个数 <= 10000
 */
@objcMembers class ProblemOffer55_2: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(9)
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        print(isBalancedD(root))
        
        let root1 = TreeNode(1)
        root1.left = TreeNode(2)
        root1.left?.left = TreeNode(3)
        root1.left?.left?.left = TreeNode(4)
        root1.left?.left?.right = TreeNode(4)
        root1.left?.right = TreeNode(3)
        
        root1.right = TreeNode(2)
        
        print(isBalancedD(root1))
    }
    func isBalanced(_ root: TreeNode?) -> Bool {
        return isBalancedB(root) != -1
    }
    /*
     深度优先：
     */
    func isBalancedB(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        
        let lDeep = isBalancedB(root?.left)
        if  lDeep == -1 {
            return -1
        }
        let rDeep = isBalancedB(root?.right)
        if  rDeep == -1 {
            return -1
        }
        
        if (lDeep - rDeep) <= 1 && (lDeep - rDeep) >= -1 {
            return max(lDeep, rDeep) + 1
        }
        return -1
    }
    
    /*
     广度优先：
     */
    func isBalancedD(_ root: TreeNode?) -> Bool {
        if root == nil {
            return false
        }
        var n = 1
        var list:[TreeNode] = [root!]
        var first = false
        var node: TreeNode?
        while list.isEmpty == false {
            if n != list.count {
                if first == false {
                    first = true
                } else {
                    return false
                }
            } 
            for _ in 0..<n {
                node = list.removeFirst()
                if node?.left != nil {
                    list.append(node!.left!)
                }
                if node?.right != nil {
                    list.append(node!.right!)
                }
            }
            n *= 2
        }
        
        return true
    }
}
